#include "train.h"

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        priority_queue<int, vector<int>, greater<int>>pq1, pq2;//用小根堆来快速选择前candidates和后candidates中代价最小的工人
        priority_queue<int>pq; //大根堆来直接得到所有工人中代价前k个最小的

        int n = costs.size();
        long long sum = 0;
        if (2 * candidates >= n || k == n) {//这个条件满足等同于直接在所有工人中选k个代价最小的(用大根堆) 此时candidates毫无意义
            for (auto & c : costs) {
                sum += c;
                pq.emplace(c); //插入
                if (pq.size() > k) {
                    sum -= pq.top();//保证留下的是小的元素
                    pq.pop(); //清除堆中最大元素
                }
            }
            return sum;
        }

        //上个if不满足 表示前后candidates个工人必不会相交

        int low = candidates - 1, high = n - candidates;
        for (int i = 0; i < candidates; i++) {
            pq1.emplace(costs[i]); //构建前candidates代价最小的工人
            pq2.emplace(costs[n - i - 1]);
        }
        while (k) {
            if (!pq1.empty() && pq1.top() <= pq2.top()) {
                sum += pq1.top();
                pq1.pop();
                if (low + 1 < high) {
                    pq1.emplace(costs[++low]);//防止前后candidates个工人重叠             
                }
                k--;
            }
            else {
                sum += pq2.top();
                pq2.pop();
                if (low + 1 < high) {
                    pq2.emplace(costs[--high]);//防止前后candidates个工人重叠               
                }
                k--;
            }
        }
        return sum;
    }
};



